package com.javabasic.algorithm.leetcode;

import java.util.Arrays;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/6/11 22:46
 */
public class 咒语和药水的成功对数 {

    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int len = spells.length;

        int[] result = new int[len];

        int potionLen = potions.length;

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < potionLen; j++) {
                if (1L * spells[i] * potions[j] >= success) {
                    result[i]++;
                }
            }
        }
        return result;
    }

    public int[] successfulPairs1(int[] spells, int[] potions, long success) {
        int len = spells.length;

        int[] result = new int[len];

        int potionLen = potions.length;

        long[] num = new long[potionLen];
        for (int i = 0; i < potionLen; i++) {
            if (success % potions[i] == 0) {
                num[i] = success / potions[i];
            } else {
                num[i] = success / potions[i] + 1;
            }
        }

        Arrays.sort(num);

        // for (long x : num) {
        //     System.out.println(x);
        // }

        for (int i = 0; i < len; i++) {
            result[i] = findIndex(num, spells[i]);
            // System.out.println("result[i] = " + result[i]);
        }

        return result;
    }

    /**
     * 二分法求上界
     * @param num
     * @param spell
     * @return
     */
    private int findIndex(long[] num, int spell) {
        int left = 0;
        int right = num.length;
        int mid;
        while (left < right) {
            mid = left + ((right - left) >> 1);
            // System.out.println("mid = " + mid + " spell = " + spell + " " + left + " " + right);
            if (num[mid] > spell) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
/*
[5,1,3]
[1,2,3,4,5]
7
[3,1,2]
[8,5,8]
16
[56029,39759,11542,85170,95989,20920,68729,33661,6800,40169,67278,49278,20991,30077,11317,26005,6472,20781,66087,76437,18280,29948,20501,86720,44165,44744,57600,91555,76962,25738,6462,9878,74373,59864,96227,45111,49909,5251,44454,93449,65551,25378,19317,88784,78096,21799,76916,2968,25597,85909,66433,30293,69683,83371,26369,62625,45474,76244,14660,71429,89672,65452,61700,2057,60003,73712,41126,74674,56909,146,82767,93324,11951,23116,16913,9170,43279,15270,29438,76151,31771,2011,17329,97735,68065,42884,99388,88209,15022,23053,49075,72160,45745,91955,37631,1977,21421,83647,16079,55281,69343,64213,99301,66886,66089,28786,9818,31351,37524,47653,27572,4953,67844,82840,80010,1802,89017,63780,24729,73723,88021,8985,53187,10646,8200,41925,34313,87107,83850,30375,86506,55096,86109,1749,20403,75909,55336,28349,5015,23182,86181,93949,80938,66234,1929,66729,27546,46754,36693,28648,12400,33503,45146,32117,52447,57291,21665,31865,59714,75297,87268,71968,37515,88077,15858,58991,22082,37721,78059,69899,2435,89564,81934,73558,60535,54155,7579,79964,19801,41110,92093,25193,28615,94522,89469,28906,75227,37615,1123,8682,58154,62898,50606,8713,18772,95549,46917,7586,69580,86764,73687,89630,28095,50748,2119,20109,13575,65533,25750,89021,34144,63652,93698,13531,10140,74261,49746,36139,28903,57648,30198,13167,77787,16058,43313,8453,37468,6162,84465,93930,72880,57901,17188,63126,62094,28791,43818,2528,2180,41452,94897,91936,44043,43099,80874,28367,93056,34350,44978,5113,10330,2393,26132,49864,49745,87355,23634,8365,45156,33255,84626,26950,74226,97259,47924,82262,80938,56474,40632,32621,23163,16778,67405,32194,72549,10810,90937,51971,19431,54907,20710,73925,55168,31882,15936,86890,86941,11023,46633,94873,84931,81322,84388,15334,49217,29605,66300,35545,45659,29249,87604,99669,358,30241,2575,77792,78682,93947,21528,25573,35586,6148,71351,59337,87793,22507,85785,38678,88133,2570,20020,81986,64985,33897,35377,71333,87180,43614,10844,96753,82621,78953,90765,51369,29075,471,43059,73770,74896,81339,62482,57511,83631,24148,67960,64368,51636,32948,80167,91964,22269,72701,97410,94999,19185,58997,63916,49464,45266,61196,37973,84968,2008,35775,74667,77932,81052,43697,52259,3043,3821,54093,36991,92055,41680,54585,44457,41915,30274,6710,52735,13710,20317,34186,21449,79213,85703,32717,81005,83364,40336,86192,61613,73765,39887,49091,89266,92105,2281,12125,58272,96816,12174,69427,33302,24488,72026,99400,97968,14013,86378,5606,34814,43714,15702,7520,61284,86246,56947,19978,4102,3282,43695,39528,25738,58015,68721,13662,29562,28710,15677,8141,11978,34861,99162,18280,58288,64663,74722,70197,45109,35216,44838,1200,90488,90508,74232,58006,89952,3031,77355,67890,99516,50777,26326,4324,33129,62546,41581,92541,3170,17088,71694,36324,19756,46863,86380,97855,44996,78349,17565,46405,11143,46257,2968,92257,98961,20881,34466,1008,55759,76520,96736,4761,34027,49696,40101,36180,55518,13516,30009,32157,52979,82625,14903,12880,11528,97732,29067,77574,56040,39457,15744,21880,98692,69605,81424,26995,17121,69920,92763,44127,72040,9993,48341,66141,34146,8580,50755,45702,82680,981,63002,29197,16576,8078,73575,43707,66520,67813,53374,63302,81266,20119,38882,51762,22753,89314,94538,99914,64698,63268,78174,33206,87783,61883,52980,72571,6760,18897,47011,41565,63299,16422,48361,82519,82965,21284,2630,46200,40267,78206,27619,57155,30937,11575,29986,70229,48834,84534,78637,90759,41147,61241,57802,5447,65604,76221,24528,8601,40234,41779,66054,58426,55029,6200,87968,21520,89688,63995,24461,20409,8573,48887,43948,79518,51855,33413,77148,38392,25604,47700,95481,59136,80722,29150,40885,13635,34424,25679,34699,37235,4337,83347,35343,26497,22161,20182,15486,65204,16419,19090,29057,68419,63359,2473,25445,25859,3893,1485,55283,97166,39848,36153,7421,66947,83001,69354,37611,97639,12230,25017,17742,34819,4122,92534,15266,98079,14273,8998,92158,4612,58292,82085,35880,69717,32478,85746,40470,10423,38723,40295,56103,65551,30038,86229,27701,31426,22513,56633,65134,68424,65503,50448,60362,34814,81249,97486,21459,6422,88858,17390,62767,12362,56136,4177,50690,29770,39010,46682,83596,23032,45207,86651,96975,58942,72103,89048,62381,24650,79483,28817,25179,65198,68617,83620,20175,5193,61878,33638,52085,54018,24251,83848,92207,14583,9524,39144,980,54412,13159,91250,31391,60706,5334,48618,95133,85479,52526,30787,80371,4290,12726,27317,64648,66817,18207,48948,36686,18244,54804,13352,5905,66852,83842,62729,53094,43254,89386,83643,76125,17994,36503,75302,13148,75514,49343,75490,16961,8063,71208,46950,66730,56382,92041,75691,26470,65754,27599,41975,88402,31418,61457,9530,82408,79662,16655,66521,82093,10677,80705,5199,21753,77585,80634,60078,98624,99940,21864,93763,3541,48419,2152,90442,39457,51192,26919,67234,74683,65514,3594,96780,40975,22167,8164,17456,96402,24118,71099,99797,74236,15922,74422,16790,60842,478,66252,22809,7977,8638,40055,77689,84004,81267,28472,77621,19934,84233,21495,91157,7211,12957,97686,2684,78660,14672,34711,63122,60832,25867,4378,80520,37704,81378,64293,93029,65561,72036,55957,93692,67736,2960,38824,13943,32892,88350,232,26660,98807,54588,961,65063,56247,52538,7394,51507,76263,40668,14319,51308,95587,25930,52635,52941,70229,68992,35377,9734,58713,90466,23436,62085,90401,76796,35570,11891,18872,37222,7033,7293,84174,48155,94539,36383,10358,28175,23713,49616,53788,34462,83378,83610,92896,73485,71416,5221,65515,14895,79211,34422,47151,53393,79997,49827,83514,23843,650,22598,45300,1813,90858,54224,79878,70720,28054,77814,32017,78068,43572,9039,60016,71053,45081,22572,52270,43165,50310,45032,61023,51921,59705,70437,60200,11503,45518,24937,76597,53325,47457,35476,26689,9134,72652,95508,68941,87993,38226,67043,18812,23657,12107,50136,92356,6498,36141,44827,75349,27027,37173,50977,85985,11925,43174,91295,55444,6798,41141,93053,76060,65666,31584,9136,56894,23211,42856,94172,75530,14536,8642,91502,26177,67122,27881,10844,65055,49441,37645,5545,77600,16520,51971,12637,56058,61081,81367,87029,23242,62872,99675,6464,52040,1614,25132,47391,59612,41185,5200,30265,29184,23609,67053,30481,75503,92000,93856,24591,1065,28522,37927,60129,95947,68574,69337,11685,72562,47618,66707,92807,51165,92954,68291,52980,31993,39602,93147,19359,16420,81906,57307,81461,35232,63273,46298,64865,1572,90520,3671,16054,47307,76651,85773,26985,41846,5801,7522,75371,5633,36210,25665,14345,65401,67686,75285,73579,78855,72221,29009,96842,61154,68990,27927,50431,94199,92429,78545,3393,73847,90425,57069,59320,80638,75669,55584,58708,54066,14452,80199,73113,20547,42671,96360,26190,40982,77955,9345,89995,50122,13254,11556,65943,67227,99408,33866,28212,44675,48221,47391,21821,86859,43503,81085,37884,7340,70833,4085,51104,50430,9579,15957,40911,28375,91826,60712,1607,44500,12019,53576,91347,7411,89258,56125,22973,2832,38992,62180,92297,68232,28347,63274,93577,85264,9318,90952,56588,5370,35005,54134,85323,15970,56774,14200,24024,8226,81491,23220,82961,81453,39717,15939,44276,2429,15669,95286,65896,5643,91923,96487,5923,57612,91484,69261,96808,69961,72678,29605,39783,98435,26742,82266,9358,17984,29643,93887,17746,35758,75071,33145,17438,50095,74282,15652,11644,49320,76917,30631,83502,40861,7343,66589,70074,66613,7587,11306,42000,9825,27457,8569,50701,6396,35299,71037,48615,5847,79239,54869,95229,49542,48161,45336,69662,28150,2520,19127,98323,45112,99800,86166,68937,7658,26802,87844,40527,84108,97019,99998,6703,41199,95462,1468,55302,37866,51087,13539,14659,58874,28032,87605,16971,11948,89916,47710,87355,38036,97989,22449,9034,60601,78988,58262,65550,67997,28755,7092,29545,99895,49311,70004,92336,88691,44841,79677,96774,20760,15941,1521,70420,97259,51711,84251,30379,72926,18995,95044,27004,93613,74365,78028,72537,8701,80279,88948,61127,55020,1950,65190,61104,13401,54539,41155,89398,46422,68370,21265,88721,17115,83055,75777,44443,8113,29437,8438,2345,95874,42162,53029,18178,6678,13178,71587,23145,74846,16267,27094,19167,17209,88777,58193,71183,80505,68087,93351,86332,78496,16386,29505,46560,23685,83427,65638,84344,5476,8734,34704,56272,66916,92341,80085,26230,82881,52476,60598,39227,52097,47241,81817,72462,7038,94658,13382,37618,94575,39523,56797,10182,9869,11637,73283,81406,55651,68273,19611,23346,25650,81427,13184,72002,5221,4608,55762,25183,3337,55806,77851,27608,38100,43657,27185,31915,74250,13828,84286,1749,46907,46435,73547,61247,22595,15888,91415,8829,92843,91980,7698,91097,51886,62872,51772,51568,87913,58487,58975,87635,55729,52660,64693,32939,86446,86198,55287,81307,48240,12558,95715,7398,89349,6907,51851,90733,96962,31640,38851,57825,11822,43196,17070,8556,18970,37852,28979,83432,90681,95553,62331,20390,10673,59450,56593,88300,37717,34771,81464,5514,71853,57942,95283,45931,33206,21821,15219,37316,71143,93215,71059,9663,67501,51108,47066,38395,91403,7050,29218,23296,18603,10541,78423,44661,80269,46690,3652,82396,89146,84237,28771,22902,52574,7241,65754,28473,92606,7287,72310,30475,57343,85219,68620,255,72628,39668,48910,1059,3857,34582,65902,90242,39453,39000,24200,58176,61802,9171,20020,52329,31540,96119,42046,46012,94883,15838,98001,6586,61257,44685,77587,61287,96778,42532,38786,14927,24749,23696,87708,88965,98936,3811,41319,45341,1941,98438,71126,41025,55583,78908,23417,33807,45760,95165,33341,67406,21491,66693,44395,92176,46446,68152,4468,33773,44968,54121,25273,14312,63836,42639,62689,33527,76660,19279,87055,53173,50746,19253,54992,40768,39269,35346,89139,76601,41959,97079,67966,10508,7628,76352,50515,57820,45427,7421,67594,91900,67479,31176,49354,38304,88659,55234,82938,71764,47858,78189,66673,86496,68207,97743,5208,11440,1641,28254,5828,54012,15227,38772,53136,77811,59797,18832,84590,9888,98651,56657,31395,79388,50395,69622,9557,62349,39064,19145,36172,76890,39930,58764,65991,28085,88639,45550,75384,69137,64315,54125,20636,2628,40613,99915,74430,41523,23949,22022,64711,77265,2241,31172,98003,4851,99573,88946,71939,99383,44023,82474,10280,57638,23432,79247,74747,97211,1388,85142,25009,69027,88746,67129,29259,49538,31595,70298,17581,48951,49983,69140,66407,39470,2485,24797,536,79984,18949,18346,53213,68910,73149,47068,9572,35074,32271,39130,17517,64532,6041,64236,22499,93853,94953,96822,37885,79483,21604,47101,10140,12096,6060,58939,81835,17037,13110,19344,32498,32321,74672,81437,24187,57243,51002,62190,28390,39669,47914,71697,33114,87523,16760,62609,78189,51898,85109,21507,45054,71377,93470,26218,94891,614,12088,18874,27414,60013,86921,93377,94963,97536,67425,62509,18464,93767,69312,90944,9031,35721,17887,90503,58095,90778,80133,80571,6207,22249,62138,83219,52619,45085,43115,16029,10056,27646,11498,32027,30925,13792,78326,89811,75699,83693,15212,20315,38248,30019,81259,67108,59241,57771,5068,72517,595,67648,9375,2473,83813,41098,32101,24406,59556,64248,42910,41592,70193,45154,14952,79394,50421,94010,29395,62559,92571,44602,65196,30905,94528,41094,165,45243,54654,45431,68568,12506,13753,46117,67047,70688,48022,83393,43166,93342,17462,89902,11843,58965,78529,97531,98963,75452,57640,15622,89242,28787,83311,34599,51671,28946,65333,14243,91739,95290,23169,68313,57612,54136,67983,70937,5602,47895,19365,98114,62152,95223,34611,83310,86441,78918,11187,31956,5907,11801,38783,93257,71133,61909,95557,31197,29543,17236,39622,43335,59842,41661,32252,70037,31733,12369,33560,4965,71279,61650,49773,62533,12816,7253,93399,43473,46402,42252,96302,91516,40625,42177,74127,34720,19737,43133,90961,86321,92806,35175,59056,31340,12581,94163,90606,48778,4891,97812,16143,88230,5544,14893,88966,23563,57755,9256,69840,92916,28177,62833,33839,31270,36061,24127,5257,44667,11428,38509,10544,52233,15302,14986,74482,60964,21053,4104,41799,91771,52428,68707,4994,23465,19162,84657,75083,88053,79849,88669,59885,66048,66483,37876,62455,46057,88807,49201,24961,43539,99733,19156,11790,99347,81627,53464,20543,9613,41993,8509,28136,40904,64146,77173,75795,4858,46822,17399,95180,55188,96387,63013,65813,59783,16645,28716,83768,73478,60248,72215,90672,98566,99807,24384,36824,6665,29301,7469,81265,82790,26420,50950,46958,74917,41131,89667,88462,28824,88215,11229,29496,56124,60382,23061,28035,48046,29963,5395,45670,31939,74165,72557,91631,42358,6325,11506,36028,47290,90338,31504,68492,21960,91578,31426,34869,53245,89548,35423,72969,651,89155,18133,16749,50512,82956,56122,4601,42572,14257,61923,83877,74764,24097,52612,24569,70074,65616,57779,2930,18287,76821,35002,95462,18557,26470,23570,47605,1255,55579,27803,30185,24009,44944,72056,37984,70415,80092,74679,45673,89748,1313,45490,58408,22164,13463,99424,9969,34541,62799,62799,90633,92593,83490,57500,47800,23534,12057,40160,44005,93959,73799,22738,47468,7213,65485,86496,81894,67046,67638,36991,24631,72138,28022,91790,93555,28819,70986,1713,38786,95105,33607,57043,70594,17942,20584,70022,17925,23554,57919,26495,80657,73806,75454,67963,25713,1661,16678,46103,61213,42710,65734,50885,52400,74000,90152,37210,59745,3351,70850,27272,23733,60409,37832,74898,30565,64101,88698,7294,56725,87641,70788,19398,27270,82752,8077,94768,40459,7798,45772,3224,46177,25642,92588,77094,50069,5467,91671,33835,11013,78186,43177,1491,12114,52318,20003,12264,55178,47837,24582,71478,77580,10112,43188,10241,83521,75414,21115,79691,35371,60921,47489,79748,19287,90004,45877,67125,41019,48955,21044,66868,34336,82872,35987,732,15134,84735,97404,17042,57293,51043,93559,45142,82301,65662,31767,55126,17092,44553,24606,8033,62685,16235,1618,48879,90920,92601,12791,17922,23176,66885,56677,64280,21843,51329,98105,2702,16128,57006,16366,44348,19386,88331,68598,27763,97286,54807,42072,78978,37582,68290,28645,10859,86059,95299,5905,44284,24061,51657,24341,75183,92347,92056,47901,33201,19752,44798,91519,81183,74647,65819,85306,1816,5298,70544,71952,171,52838,18722,19780,35096,53788,90536,90658,16768,9665,83952,3779,23560,29574,41230,49720,57897,49847,25959,96498,17680,13522,57904,1166,84769,57107,38340,77834,23511,66604,56612,65391,26294,48073,52322,52561,92129,79597,83147,94862,70461,92612,25859,39442,3483,2324,62826,57518,95829,47824,72164,73361,97450,75888,36593,20584,10345,80701,81199,43010,92396,28426,78619,38330,67191,90133,40178,62510,35775,55779,90774,76422,59622,11692,64618,87020,94360,8640,50979,28356,24180,28911,98034,29746,81385,32681,78787,10099,56462,39969,36513,40000,1278,63476,18576,89123,72040,68100,98238,6530,39948,26945,32117,60644,19767,32027,77739,44618,98266,52028,73242,22633,72333,55387,85028,71844,83522,70987,67229,37434,84963,66920,37413,25058,93687,13250,42222,76070,87916,40787,76462,41753,68415,42935,30863,66974,72376,56920,94887,66647,54600,6738,27085,24856,38779,73204,67657,35832,81716,16133,22128,93976,29954,75691,55023,84847,74594,88451,88150,27539,45589,46046,73273,758,33164,92954,57015,73272,22456,99899,82682,87065,37794,11654,22852,34623,24522,21025,72338,2320,73012,88358,3392,94530,39001,58491,18734,36100,4358,47915,82866,33571,22784,56705,66860,70580,80329,32956,12052,11319,96649,23710,74180,266,34425,52818,63430,14016,34601,55880,13910,20286,57759,40219,65467,40576,94550,44872,31246,24934,31042,24211,22180,15481,44042,61070,76618,89633,53610,12250,29471,25909,48661,68293,31504,82830,80058,70506,79332,10482,26539,43665,54711,63581,18013,32148,36463,425,37950,70336,23697,82200,69995,7751,83411,84584,77045,16934,75529,29845,31765,35940,79478,5976,32853,45938,28390,7852,24879,97760,68584,34040,70459,24535,69012,75175,33276,35940,60738,7524,9945,15760,22147,35671,45519,64241,84363,61656,64050,40180,64487,59781,73317,67690,90694,85611,29772,92743,61519,98998,2353,49421,22680,32671,89457,74913,44113,9415,52963,2040,14727,15299,56338,58695,17255,60330,68074,58604,72914,6809,18694,33228,31538,36943,5522,70095,79703,29009,27452,84042,12415,17391,64439,20403,1728,37594,26154,24201,35699,63703,86395,46006,68909,47554,81345,80868,58599,38370,86153,2517,49665,95570,10371,40292,62235,93163,429,3229,56525,376,31241,45377,25780,14308,66123,34148,87556,69610,90195,21059,33326,77057,45602,35207,57742,61935,56813,15753,25232,10643,78826,60604,71344,41699,16153,63555,67824,57558,2243,22921,20333,9389,34422,61212,61889,81140,36075,74672,64470,74039,54936,34255,24137,77335,13945,6135,669,54979,94531,98423,67257,98324,83642,92973,11417,45066,57075,56337,21880,6958,18965,13239,40632,49076,57188,25010,96678,7612,50867,13719,41921,61387,32938,96126,17868,10918,90542,65724,4570,16166,94316,59214,89466,44332,60460,75362,78407,19993,69455,62697,46887,65751,23457,5201,58599,72285,18261,25382,29433,96398,44229,30627,65417,87468,90133,22489,4364,13914,93439,84065,67345,21653,44697,3130,49100,74661,22708,26597,1174,5841,40647,32548,2981,6768,86914,65255,7442,30068,25733,43129,70980,9363,69342,68809,37072,68589,61858,6183,65383,45878,99264,46649,68908,52775,58102,84788,59230,43689,97071,38279,59046,7671,4318,15711,87990,16861,11926,31843,56875,23523,65395,17768,1372,53270,9809,34844,90403,50458,40946,10489,67376,82782,8541,1924,34508,1905,15459,86156,50884,85511,2107,58606,97511,10558,23063,61895,14129,77645,68007,503,86082,89301,16073,23777,1183,98953,64646,81825,30434,67319,62695,82947,12229,74596,24095,30376,46242,25430,98234,15475,4692,75184,58315,72018,92216,90749,24279,68772,18515,29500,40214,87581,45573,35074,60994,70004,13471,45935,12758,8944,39019,61517,73087,74205,50308,71812,55403,61784,33442,81775,58721,69133,33224,54853,33167,79553,22296,38181,83473,32283,63398,40520,95652,92949,46621,81884,53018,54823,36060,24694,86320,52606,18247,8775,83852,6609,59028,5162,51915,75424,51943,84864,34833,89032,91195,15059,47974,60214,66647,66959,26142,28485,45317,65448,74235,156,17891,12646,66948,9001,79634,10484,79334,28607,28648,20493,50580,54761,11605,29411,17782,23157,70104,16711,43105,90340,36751,54007,41707,62327,26069,18212,31946,91048,34387,68733,24865,14471,6740,93888,27321,89283,37099,65438,76695,25828,79410,89960,85347,63536,24597,1918,71368,61808,2013,21871,23468,2386,80585,94488,50236,2447,482,26986,57207,696,35414,96289,70207,51747,95805,1668,2046,10365,54761,79113,72177,33759,76018,25011,68194,33188,97559,49252,58719,46803,2129,40135,5535,45376,6159,90471,22671,82823,14089,30342,14944,89676,58283,47972,70101,3852,95016,57234,79524,64905,33278,30856,37692,19552,16916,97030,86874,410,83305,66658,28773,11425,4141,37139,55766,72235,3971,86430,81488,19281,43625,83117,34530,54556,39998,27815,54755,36539,79944,4662,43237,49738,34819,77464,40518,64001,21489,46518,33010,4496,9076,24651,46945,14035,98715,47371,15317,25857,37135,45881,87370,55796,42592,57573,5321,58787,9483,49027,2896,57448,97615,6433,15913,33759,56771,36098,87271,78184,40731,579,11738,44992,90162,29093,47132,78000,60331,19539,30455,12702,79396,81478,21536,5926,2280,10043,25355,47055,64976,82994,22657,54061,95445,17356,92174,35234,58308,99691,23243,63951,92120,44572,45665,94605,41627,72205,39196,51464,31532,80892,81295,69248,55665,2368,29829,11227,45782,85460,84834,79824,6921,40106,88341,12447,16129,81150,94596,97665,488,78837,79419,31812,95353,50616,31527,53325,65991,71453,94756,77161,2248,29133,59263,25747,88124,9856,5665,8816,30871,90599,72226,61230,61068,28633,17843,12355,58021,39226,39127,36281,2363,8323,83091,26559,81831,18054,7876,50532,88490,91632,75335,85124,18357,92881,31343,99870,83771,68723,15621,68652,67068,3100,42638,64009,31978,34028,15227,37097,19874,4459,37930,38542,97636,49644,65371,39423,55102,44594,3379,99929,97608,13692,22876,52285,3666,72833,2303,95286,32538,13717,22507,49634,50295,3310,5810,21855,16350,25575,60927,10534,34412,87772,27796,49072,24176,92191,99881,22264,11175,11305,40489,26943,69045,36866,78822,47148,14179,9281,13100,22182,358,12522,94895,61171,56281,58322,95084,38089,15414,53858,85925,96026,75095,9840,42094,79194,33750,60782,59297,44329,90013,87112,92176,19859,92733,77624,71805,59977,71911,28225,64377,7535,90873,49831,98087,1911,37245,28337,84791,86111,57119,89138,95309,50585,79668,52103,65359,3532,4040,88772,43290,51151,67799,92890,97114,73338,94081,6614,93840,94937,5829,66868,89604,6352,98687,89920,89874,12950,85569,23398,80928,24414,51625,99554,12550,70944,26223,48831,34656,79565,59142,868,15761,26357,72034,93468,77507,76221,73705,6440,5732,56066,12796,49912,77123,56061,94417,43071,3536,11267,53731,67569,36714,84341,59245,14105,86338,80513,94216,89511,70416,85135,60332,63494,50615,61972,93257,6739,98175,88954,52146,88427,20352,69371,38158,13859,15443,49614,37498,15195,5810,99456,90792,67756,69949,26734,4425,22971,94767,56532,76097,60608,25173,21348,77441,51399,33102,4461,65925,84438,95671,6113,33464,80070,92529,47177,38294,60319,76390,10173,6518,80997,19524,17927,1883,19675,89673,80056,34776,78698,61741,9992,23918,86696,51961,86987,95149,78822,91182,96172,19376,17555,3097,25823,33105,40023,88107,18377,91124,53371,15774,35241,21995,48707,75234,24854,20970,27749,41643,8663,57771,99661,76205,20346,50268,26223,20207,10530,21704,82062,316,31386,64801,12967,52097,72208,5364,76176,70543,27625,62722,73803,49590,55629,13685,99572,98381,95159,96284,42506,42676,4013,73975,73456,19123,84806,99068,47010,60934,51301,59515,7262,24665,4898,57978,92002,77775,89035,95113,66419,85719,13233,19804,60481,3661,98875,86333,56883,36782,85653,2451,4516,38305,11063,68005,91592,92843,445,84157,84203,70638,58137,53331,72281,25547,59524,97012,88119,67060,58942,20496,37887,67033,73927,96177,85352,75360,96069,92721,97777,79365,97873,54699,80284,69643,48731,55299,28782,28250,98278,26018,43575,11391,794,28182,88696,14677,76414,72445,25594,79151,91731,94114,31159,23295,75685,55755,36962,98780,10980,8355,92490,34069,18535,5263,55813,89592,16983,4283,37911,11527,22251,52704,80028,12314,73728,13559,67786,83217,97567,72229,89358,59959,95459,15027,90685,91867,43179,64342,25131,79926,7232,28863,24584,39537,63556,696,20271,73672,56812,68499,21446,1062,61225,5243,87925,84464,12524,18424,69991,59895,43799,29360,79219,15019,15448,58464,81248,72223,64803,4604,811,95975,59912,35316,47990,949,40741,93355,44591,30190,42476,78625,3051,21958,83421,44772,76150,73707,11136,54752,76303,58438,91744,33917,14151,90587,90893,24815,90214,32946,13417,85978,85528,18444,48423,69999,60695,40053,30048,58767,95756,47535,79057,76729,30305,82526,42154,32514,50407,45219,37901,28804,89042,35393,7354,52723,63807,85784,23595,98165,77121,96022,1644,65226,1206,46271,2633,41197,47003,83479,87603,99230,77229,16188,15747,14309,87605,57842,56781,4519,96970,2685,27968,97792,19309,22827,83056,79670,98702,9549,27375,29196,30247,36944,24260,6844,34839,93892,48468,8031,50917,46650,26031,30697,19829,98336,37899,44597,73917,84678,92170,70618,21981,89187,85633,93081,81399,92805,76687,72113,35143,84376,98351,66128,33802,38227,42787,47210,92177,3698,7627,21226,72646,65046,61196,24749,84698,90634,92467,66182,8519,59533,42827,8417,47665,20001,8442,3144,96704,13999,49706,40011,73774,61748,3240,40431,14772,4966,8398,70591,35998,61642,52467,64507,37195,80093,91890,62353,79945,61933,91259,67975,9936,93183,1582,72435,99745,83902,56692,33122,68274,92487,23489,40774,96148,86372,70330,15137,57170,54837,7669,51534,67498,69360,61776,81591,75396,11125,70006,41341,34416,48850,4734,94611,44341,82206,43544,15126,83456,48449,26030,34030,30783,4855,14118,77170,35548,52056,85217,79509,6464,77716,3298,91219,30427,46036,22555,49483,43187,30251,58130,39429,6431,87617,78140,95321,29629,34187,98040,59208,31953,39957,21194,25799,26458,84142,93141,60023,45796,66452,49204,98276,5107,13930,77761,40474,40065,24202,57244,22746,50500,56200,98866,61208,46761,28686,28952,12236,31095,94914,38768,77211,83824,51018,72030,45545,35362,99794,92325,20268,87976,13986,65418,73271,60188,85023,92564,68058,74909,21751,20056,88683,79179,94666,92748,51362,69554,15230,64639,91834,50703,7715,80172,25813,75561,40320,35801,43085,95753,50041,70690,42285,87566,71378,67491,54696,1879,87582,74009,78535,55764,64878,61199,30477,14878,50043,12125,8898,55781,97277,36756,75709,92482,87101,96687,50202,80971,13965,6164,53314,61842,79940,54002,52058,7568,42385,45665,82310,74157,4836,5699,48077,1699,38537,10426,79315,31634,64551,22474,88504,9305,18654,72288,30211,29718,71684,1517,48956,97449,38989,36717,38765,92104,97600,66113,51110,107,19073,10013,54605,83653,96818,96199,5264,2423,72115,2620,53045,58019,6083,2167,15703,80137,68096,97550,53609,42928,91192,55640,73272,93464,70827,98987,80731,51186,13892,8840,23462,38013,49399,21601,36209,42355,37249,70651,23017,18062,82265,78332,85631,70260,86224,34374,17578,42959,95177,76325,82114,12988,79337,86125,45839,15969,55808,10403,89305,43316,54041,26388,29467,54671,28571,4955,83224,47382,81747,47261,32052,87919,2177,6915,6321,55899,72662,23223,71420,92235,65439,27689,92437,30712,64128,4131,95193,5928,14737,66988,83436,32212,75210,84865,91267,49899,99522,11967,81775,25883,39194,7342,28955,59852,41489,72354,47530,50105,12192,61821,56341,12857,35867,72339,30057,74576,5796,68754,3237,53346,66556,86108,17714,8779,7236,6351,48812,67088,2597,21113,96524,62221,5520,21688,85513,97615,65902,90646,84852,81322,49302,53987,5830,52419,5385,64258,73001,31834,89617,86809,51355,15708,7911,74483,92044,81764,10520,91200,36517,37326,37077,81239,31411,27728,7649,79496,16233,61309,59061,30483,88112,68622,10023,83959,58654,51340,69194,73180,44402,85072,61083,30002,12492,63924,76487,24271,97069,82442,51987,15718,41224,33897,16288,52595,65073,25184,98592,82155,93849,43229,69185,84563,96672,25748,71366,46134,64512,34887,57746,34496,98492,84318,96018,20060,78295,58316,21773,11039,55350,21858,95384,89743,56613,80085,40320,62790,40801,76026,68239,83170,91449,39514,94966,77106,94745,6437,60368,88120,61609,40978,64682,15849,90551,80794,9326,93578,8853,96824,21802,43746,69781,65204,9045,25362,24363,1104,15827,21131,65039,70389,3535,79165,81251,66109,64538,56485,57805,99984,8505,48944,48799,61390,51724,16835,35046,51465,7656,97067,82952,78341,76739,87551,21615,56999,60410,99023,24412,82686,1492,30834,49877,23157,34623,3889,43946,67201,74228,84484,21456,26818,22581,52101,77183,23139,47762,96954,98129,59692,31179,9641,4978,44284,2184,60591,63738,10587,29269,77139,13643,95661,84580,42885,31570,20016,28833,90780,34991,4601,66815,31030,31204,84465,9753,36441,93153,95845,4277,15894,1249,52584,80007,95988,64869,86809,59187,62828,98197,57300,17325,12403,65452,92925,9082,57880,89933,24639,25347,26544,47603,6196,99657,481,95573,34021,26839,78178,53644,42198,73984,35885,91446,48890,93323,59743,5562,32249,83390,48008,75784,30347,98638,62594,20680,6129,75677,42543,76955,44166,52024,46194,33293,77505,55921,70664,69402,11628,54524,45056,52185,88069,50921,12380,49536,97059,50406,21459,89149,23221,81997,28181,63678,8726,40519,7082,56142,29331,49795,8743,7864,5343,21560,12115,98138,10035,14541,18372,67435,46728,8275,4020,7726,16044,87008,67789,5714,34495,68691,23101,95206,23816,85303,88787,59114,31629,58391,55994,50296,65350,83917,3652,79774,98713,29835,2803,90860,55147,40501,62750,15810,46290,99861,39837,37767,2380,73523,76011,77842,75949,14012,99048,97843,91243,38909,45937,15068,51887,73280,11065,29182,94262,48868,42368,4868,5203,23481,46767,67067,19840,84378,5413,62393,26674,81626,91977,2891,26379,39559,8126,95291,4988,10952,95594,85731,16854,16653,19849,19969,3521,86872,62116,98980,40754,3987,41663,62134,26738,4893,55687,10081,68298,18357,21752,56645,86069,66022,89256,91391,1524,58077,24488,53567,54979,17351,40164,24573,14253,48235,29179,52679,4736,59496,51037,87764,73601,75248,28378,22024,62638,91091,88347,97855,91719,61490,72098,38943,62114,88786,96080,98840,71306,57332,69918,83526,881,94749,44817,14203,38786,89168,51388,63239,31224,23137,7022,2845,61438,59265,15020,60738,82862,78210,58774,81669,45507,62051,29970,66353,26358,74073,45358,51430,85985,18960,91629,70678,22295,38197,20347,79427,35831,11290,8861,7249,29424,45603,28980,81998,34772,4546,55657,89114,45074,42560,9888,44726,11989,52775,41408,89791,30226,19182,87422,36922,76113,58637,62185,28667,57795,3801,33909,50960,98831,32675,80279,46765,50410,76880,59630,66466,16286,14123,12144,62203,37980,20122,58348,92842,71979,37334,83913,19221,14514,32764,71936,33735,69884,74889,78972,86049,86200,89656,89737,75890,57252,71386,32185,59515,15343,8044,11531,69619,2568,62497,55201,53273,95903,55837,23591,94361,16084,41120,97922,6205,10432,24995,77455,68954,79795,34790,65968,74179,33723,81193,86284,56667,59516,97521,63841,80220,37541,65081,74671,60598,28690,15953,64483,33535,95118,85819,27529,90618,87167,27955,71085,79453,61986,30695,87876,75483,54996,42934,49822,35817,11832,65780,69763,62328,98980,7428,248,76395,86514,16435,43062,79995,26459,41282,58863,7413,2999,69054,51040,97361,38539,54465,78264,4754,64894,30391,62888,99884,50315,77241,49662,87421,78928,84781,76084,72112,9806,41780,36540,14903,2090,26599,50554,25340,18013,59759,89741,21817,22755,43985,27369,16015,83319,72485,92110,83810,3437,11848,61742,94533,94380,43529,70973,23393,19776,90333,58678,91203,93647,74577,87359,65327,5368,52478,11430,62083,15838,58850,39053,12291,12900,62223,18346,80145,7199,55289,43372,42452,84138,99756,43813,46929,67776,9420,6060,29768,93492,90880,80549,76815,88539,33903,79456,16058,45482,72162,90422,10476,16704,68472,27835,98649,57861,38807,21184,795,89254,19143,55750,33146,68835,59129,88363,75496,70995,94491,91097,77002,773,24250,72327,40370,2148,49871,48135,99281,39862,94994,83502,89304,27838,75830,61417,58515,21401,4287,33613,12926,47364,34780,49712,76549,81955,16319,74671,74577,57295,18146,94541,83198,49201,75164,16511,94083,53129,12493,86124,84540,12857,73069,61850,77364,56833,13473,30497,37500,11052,12742,41599,45186,34029,34774,36335,12337,16261,58042,65232,86414,85572,94738,83886,23257,73654,34186,33865,30734,27204,93,57571,34342,3236,33962,55256,44744,71260,34195,47781,71098,48180,57029,52231,13952,78651,62122,48185,66002,72119,48631,85140,35451,32530,89993,75656,23027,37000,78122,83061,84049,69424,45706,76572,57301,89579,23104,84839,35945,80620,55517,1049,63789,68158,18330,32603,32460,6536,71396,47000,6694,36829,81764,72881,88416,48322,79909,21133,43860,93681,37445,84580,93935,24044,85510,84865,62298,21940,54659,8430,93489,10557,96251,38977,70961,17865,68818,48003,90788,19446,55422,33797,81654,67725,13284,59066,85398,61983,77352,69560,9966,4283,96171,62949,48319,37247,85882,99377,30219,80710,50478,8544,95061,45527,87480,52058,20884,5510,2236,73148,97935,61420,44776,22789,99509,98439,3189,66156,74582,7694,51361,9521,52340,16430,2202,2533,71157,90301,98992,94419,49426,92518,25927,27956,35756,75563,22708,8987,60701,21791,62817,84325,99721,18558,39931,28714,43208,47155,52821,44084,3248,89267,25849,41198,19050,99880,82823,80600,23211,22269,81976,25998,4180,50186,37427,39092,47331,4221,90092,32396,49587,42208,98609,46567,83711,98774,42779,93303,61655,82395,88778,9120,90009,78877,67027,84685,18215,91421,16747,61193,70289,39680,70821,1743,10743,55310,46850,49982,36234,46048,42955,8631,16862,14604,19429,7305,52982,18681,2345,38873,43693,53165,35127,3046,5248,29051,66248,61329,79575,52358,77773,11980,12343,28056,78140,4715,78928,41208,24865,12867,19279,44289,60162,32912,67333,57431,44470,2980,93910,91785,48776,84871,55533,43184,13276,66040,2482,80091,67650,36125,28103,20379,66615,38908,62419,70319,51474,66358,93588,21475,19210,40894,61177,21446,91507,40267,30021,89338,31326,47671,4262,27006,31154,72934,71301,66537,39253,59806,9319,96341,26099,53580,60793,22068,93944,87385,2791,25771,64238,72272,989,67087,67856,6934,84646,42612,41692,42686,39058,5495,23114,81450,70704,50319,37071,96675,39792,3663,30352,24066,32259,63180,53411,98862,8154,53092,33497,93379,13276,35565,81796,34876,29805,78959,14667,79195,22398,71973,67698,58900,10456,25942,48804,68306,58060,64835,32242,26765,95648,78489,36609,70816,748,99974,17021,27432,7740,18694,80422,79978,18613,97264,24112,72954,36055,30742,90576,16511,38968,41653,50803,5061,97362,22535,28951,51733,32865,35265,46269,8984,39882,22655,26164,80850,80931,2678,50848,81380,95942,61396,5241,69698,95789,59400,85414,34294,32130,59377,61047,74440,26320,77804,17060,59915,48301,74937,92192,46276,21077,11276,52828,17593,70319,17044,34046,6512,97588,25399,76697,1694,4488,64550,64190,34252,50730,99234,33525,33247,58037,51018,82621,88560,65990,43782,41880,80831,23546,30545,77501,68889,25874,23800,97306,54064,39045,57931,29525,80015,9261,97412,9527,83444,25483,2908,45268,12465,87745,3445,96143,98615,18926,65809,9448,73302,39052,14428,31614,70911,64421,44274,43898,97517,37472,11874,66174,49387,74334,5273,70199,58811,89215,46834,75278,75645,51612,85286,33621,28030,20616,661,1558,80285,6414,2116,98709,84786,5540,40964,28545,7617,23682,90119,3412,62370,41537,94428,33173,27985,64097,62011,50822,14564,94588,51168,15636,80826,51698,89664,26559,74809,15852,58036,43125,97811,53689,23001,16195,54941,65871,16535,39780,12099,82566,11322,87072,33515,59175,93780,60719,56995,71553,3704,84720,75426,14837,52003,28073,48479,43519,57239,99035,24999,23379,86687,65148,58299,65417,52499,35855,79013,34531,47917,99840,60364,27086,35997,42629,42722,96295,38240,34951,66562,91809,29956,27931,34203,46752,70291,69699,14398,41444,54222,353,1728,49113,49522,56095,27693,10405,74712,19920,70112,30143,85060,11074,3042,10653,10111,72877,67433,29609,12495,52619,25115,4649,30122,46907,67950,33728,98256,45838,25134,4370,95368,28884,98872,93494,68409,55129,65851,98991,63493,91044,5735,55892,70610,63410,87992,89022,16514,50125,90702,74606,39284,58535,48068,98673,92053,81970,25472,57442,12995,22282,64639,25591,35400,67475,98243,47991,44447,57188,10756,81884,60248,94878,76053,69114,24171,92482,69168,61131,91557,55858,62844,43245,96082,79831,15116,25583,69758,95435,57840,35101,86084,938,38246,71562,66722,60315,18574,58024,13635,30697,90017,681,96488,6177,67452,79105,44681,83019,78754,30206,68400,38983,56614,7717,82743,42643,64281,4853,21007,82090,25976,41330,20136,76074,5315,82434,90588,50098,56811,9814,37191,58733,7443,99234,47211,85403,41075,66039,74374,36789,25570,56073,31789,56578,98124,72098,13164,38693,54150,67262,78500,86522,88303,77925,94185,95995,54928,46727,21320,89479,47308,385,65021,85003,46626,71676,53994,35661,80188,43681,51981,23819,82375,91198,18171,44624,10995,80759,45503,97063,91666,38957,66506,2238,8644,60878,91849,97542,93055,82637,52600,14905,68758,46549,66877,32107,27092,70763,56712,45836,66993,53,99484,76448,50048,99704,9364,87728,28699,55948,26831,48703,59854,40228,54613,46471,47978,67259,58128,97081,2594,48671,80180,2018,66181,99665,80871,5516,37735,87413,45604,87444,41653,17965,33076,70403,31273,65095,16474,39543,21987,57480,38342,16932,39485,78713,84196,11935,44329,9370,63758,5206,64374,80872,77924,10141,27911,50870,66696,1703,70582,33606,33048,25698,11058,64791,779,56225,305,17230,67254,85594,90411,36446,49082,58249,2512,68762,3560,77981,70483,69415,10273,5725,11085,15480,81423,8237,72463,708,17314,76371,46888,73473,9700,64410,47946,5123,1682,35373,88932,24678,40682,40898,25454,97216,67664,4775,17440,6128,93465,85722,73053,96461,3335,71624,6174,18403,49450,51490,93583,10698,23116,49547,88903,87854,68112,9052,92630,45573,67353,9620,1804,49127,94353,44153,19560,39949,81583,34371,26488,21477,82435,52291,40016,22650,36288,78296,1697,16969,23107,25966,18064,17425,60752,20130,89576,2119,78914,83045,72593,75214,41491,24379,14045,22141,24376,89447,3925,51679,46404,6928,75539,38711,94452,14313,7285,91868,53461,916,46716,22153,93760,31112,15150,3038,70055,74998,24347,39785,3466,66841,86532,43030,36103,45802,23499,22567,55551,88187,17535,89581,33440,40184,29824,77207,25607,81919,92747,92271,6356,17919,88715,6583,54971,14758,55040,61313,16363,38360,75834,23952,66936,63739,47278,42348,43019,11554,45601,12524,98472,82144,85147,45773,72653,17964,8624,18549,52490,4336,4943,89862,11011,42038,98275,93767,68242,82617,56227,32290,35227,87053,30919,56892,90150,89019,86989,87540,85026,90021,54339,37936,50621,41399,99367,38527,53980,5098,40761,56935,74287,42748,37288,16374,59095,57414,77033,69553,4680,12478,45193,58687,23597,93248,95300,25904,12509,43791,3875,65282,35710,43000,11610,52866,94093,31388,85261,93223,67662,51614,62404,68194,31584,28321,21730,5896,43326,69238,80062,47216,56190,79344,23769,28462,639,93001,22786,21741,2504,49706,84424,94349,42111,82050,5842,31739,2602,25564,74636,42661,42546,29117,65472,94971,38173,27588,75404,97123,409,43023,76587,75534,2302,49390,65288,31976,42022,80457,46150,23885,92659,68699,82878,14610,32030,75079,87741,69465,88663,36203,61027,25679,14083,10304,86472,1135,22690,83864,51319,13371,18298,64682,6430,52408,16544,49243,22706,46632,55030,75277,78418,25066,83668,44957,70979,33589,85402,66139,82477,49403,38196,47031,92569,75095,51880,74291,83865,71888,48010,92772,13912,37738,840,40344,8961,13088,48439,79174,80405,25237,41621,54858,32224,30351,57737,15756,8109,63214,56802,73939,50523,40748,51115,5381,96565,55914,83546,54982,31343,14267,79854,29042,89756,251,22923,24906,55076,92781,67274,65773,88210,87356,50265,69881,58709,14156,26050,15880,88832,38945,78149,98564,95971,18905,66941,31575,87649,26091,83761,86577,23952,21232,29479,12015,98800,56816,12231,35987,13580,70952,78136,33539,59341,66776,40345,82214,43345,40268,65411,99491,56126,71007,82529,63231,73082,57496,1234,46179,25667,56942,24961,33974,78263,67,4682,66865,29687,5730,27136,77173,64496,90367,9268,62501,10724,97387,52663,74731,18325,52796,85668,26301,95739,86292,23856,32960,89921,83552,61183,69437,77557,80956,77922,37814,81976,84433,99001,62641,72418,58433,50126,66719,48013,6219,43185,96441,99941,80574,30684,96650,62164,69473,30187,5033,3152,26309,58310,73688,90330,94197,51244,2121,31675,22558,90197,76606,8144,84038,4122,49014,24536,81469,4314,35751,38040,69565,9314,94542,64774,72249,43530,54682,28008,20939,13042,79459,1081,78090,97491,99064,2770,84334,11130,30611,68866,5949,99387,28135,29220,76287,29809,27731,7655,22736,899,69233,40597,73735,9580,54281,26812,74652,76703,73690,64448,58500,31256,49079,14934,27263,55043,37580,41720,36446,3977,82512,82761,6087,51845,80174,82682,75104,3341,92627,77197,51755,88933,98198,15488,44993,62824,74681,55254,99456,10154,83875,78801,55060,30676,58606,94019,62983,72368,87648,59714,32349,14820,54664,52066,33716,69134,61312,49799,42722,90844,59250,74569,28147,92114,31011,43739,3970,63215,84363,92047,83192,78277,66445,87714,87820,70335,10547,62917,64060,78065,98414,46546,1904,71420,15379,10917,89027,20109,58999,20993,51046,82449,71462,2946,2416,88467,30891,24716,47667,26249,79818,4527,4897,56940,58859,23864,26906,24193,4299,68114,148,89701,29965,21231,7967,41480,28232,65865,84467,68241,5338,85666,790,73785,89466,19728,70887,35780,27546,75661,17419,4986,64096,47133,39700,59596,90049,56030,96433,96266,99989,29013,71150,89456,26759,35849,1011,67418,31832,39078,33263,36570,21856,7140,34605,70897,11431,26483,11634,18373,69454,18018,58808,23505,11551,17425,25037,83461,48012,32448,52003,57601,55959,69302,14909,54842,95822,63875,49905,37288,25076,51391,86055,38453,13640,67344,29678,57125,86035,77248,47683,92098,34180,99542,36559,70367,11073,69523,498,10138,26608,17974,10051,96824,17501,36868,24600,86165,69132,40901,89121,99974,84607,82843,84144,25560,79490,41732,52477,90482,62165,63847,52044,60246,65249,90611,81575,76944,4520,29472,737,94909,78293,59446,48533,8094,64308,54767,2942,22010,24770,36193,11133,78215,27907,840,39547,36787,79012,3035,86228,64898,24282,11495,28383,35372,45822,42122,77777,74481,84699,38250,72654,34541,80843,4954,96543,7467,45563,60058,73020,11648,82025,99023,79778,83144,23556,75592,36916,42083,45013,52692,35664,71020,78077,58684,27861,9113,1480,65456,71294,71706,79917,36652,53071,60280,34511,49355,84860,9372,10741,90974,21229,88664,34608,28896,23306,16394,41549,33387,80989,34980,32472,35763,27789,78309,27437,16465,44714,15587,47405,93243,18709,42112,44533,86305,72322,6415,17373,9721,29184,44194,68056,74131,36322,822,6842,62168,24441,96857,21947,34682,14731,49759,16112,18123,8410,69415,98486,12736,72768,97652,9080,14623,69147,86291,86429,9706,5133,82863,22295,27938,21532,39813,92648,39390,52560,1601,60645,10739,50105,72144,92947,38583,28700,95749,39149,98344,92640,4819,72963,82869,99582,74196,76555,60696,94209,95553,26117,47470,72842,51746,82141,18733,52514,81689,55297,92556,60785,22638,4042,47558,80735,33072,70279,93584,23908,34066,79973,65237,2512,91866,49495,85192,11812,48491,79615,52213,84056,44454,40278,45556,9347,4141,94721,87968,86956,51145,47516,96064,38094,83219,57653,62117,25582,3462,79975,91041,31915,27852,56093,91169,6863,12270,77008,17005,78555,59198,6637,99109,15657,9348,8125,15869,51466,16590,56807,49782,35564,68464,66994,50809,34224,95285,12489,15978,20367,8985,6061,20758,10874,71259,20928,18598,17542,73475,67766,38938,60003,89933,86621,24365,44137,63410,15722,39611,56312,61708,72100,60734,34689,24203,17593,4647,8695,79301,1751,20410,45398,79271,93715,14274,24680,98235,40680,13064,62592,87651,30259,67428,23380,80236,61007,56590,86973,47549,87822,21621,75614,16709,21747,83714,78834,87624,66808,81085,50887,87637,12138,93268,22775,75144,35825,83275,96984,91342,37203,92347,9310,62172,93217,4299,30596,28876,46725,61543,33868,42578,18604,13715,19219,96714,31321,60429,4556,28056,37247,87136,21151,68085,28460,77335,33965,41264,62408,89007,39066,52135,32971,27218,47051,18308,39961,22031,88291,7385,86764,29784,736,90516,60941,27133,31511,52694,29455,43075,30455,13882,55807,52735,96008,69587,73410,56350,15776,99232,26860,19099,81947,82873,93364,64084,42789,38897,71070,83442,88945,47117,16315,77695,17632,84342,44823,16614,71900,61334,75944,94485,7597,22796,7764,60826,54140,10681,30926,73570,17713,87387,12009,643,58721,72105,37620,85285,92578,57733,88980,12311,74013,14873,8425,4058,35331,4594,35175,24178,89897,2966,47651,43729,14119,19583,33795,42136,23256,49354,67732,51619,69864,46567,56117,43482,41004,72432,23164,53175,79604,74737,53347,75735,83312,33037,71620,91384,58608,54662,91449,67986,67563,86982,35663,92958,10123,13640,32539,17518,63328,36742,26795,20737,86026,91197,29262,81278,79564,58029,38450,56130,20683,33902,22527,26329,37422,70675,8578,87517,66878,21589,24092,17297,75824,6798,18785,6998,28827,78089,51615,57315,71822,44322,59446,20561,4750,17718,91597,31101,75565,64153,15821,54009,94449,25606,12232,5689,55144,35859,64490,82492,33225,64694,78055,70602,97199,85037,40274,94652,91311,80712,1109,50155,70812,8159,38970,50705,87508,74723,67201,78435,63085,95960,79718,34199,74832,73919,52645,44815,44567,76127,83325,1893,41545,71461,2639,25052,69831,51285,62027,12640,10449,99366,18705,32580,38149,97510,65013,39916,60969,97264,8115,45267,98367,37156,38821,58995,53239,60430,37203,50336,99403,18680,3727,97641,61734,8143,91815,90940,91937,96777,2791,98614,78642,43238,44086,11865,9693,57698,35431,69045,65393,60208,23640,65688,14723,1584,76178,76080,74949,91163,2888,1748,19294,12397,29668,13683,84310,79451,41489,84866,97484,62694,86777,88627,94307,62750,1573,14574,66642,31053,83906,88438,43798,33262,62740,31098,69323,77780,26438,61068,15233,54007,91177,94055,94133,94171,40217,83190,32815,27674,33538,43682,59349,4824,32137,45669,97807,71882,40717,50301,74234,68584,8880,92183,84365,90980,9613,57756,78511,6392,63046,2448,90963,45810,86505,99886,26772,82487,20849,12710,46870,78288,74191,82130,71715,9440,74182,89149,17350,14915,35545,12059,98807,88013,61835,5148,87426,99969,53319,3651,285,35737,96194,3150,68810,9529,60965,53177,77629,58798,50108,17833,73068,27916,66481,98686,32997,74341,59321,57987,85493,80349,80165,81987,75075,28262,96014,25460,65949,72347,1184,36210,15830,5219,46618,49647,15728,28110,19124,46188,66607,89556,26076,76068,94294,81089,50582,62479,34854,63354,83449,78977,15183,42123,20153,25464,453,66920,64011,52153,26019,59205,77379,62275,55595,25578,79190,15635,92693,12654,88976,21714,52483,17289,33736,19534,66053,13766,68177,27587,10168,84156,30908,1765,44869,69420,52427,30359,95931,8937,72640,62404,6135,36561,37671,11659,51497,5347,69782,50823,43677,26925,82279,96502,97088,97326,28807,32912,20734,27590,13712,49406,89708,54167,5069,99766,87314,36473,15891,23392,98974,59342,95561,65271,37747,13390,59346,31820,48207,4305,61059,39573,12854,36099,64071,16961,54985,42126,25405,44782,32603,23920,36322,85621,65045,8465,87467,33205,79660,57664,40834,30649,66667,17245,82399,4675,47863,80474,34549,73461,73513,9915,90275,56661,65622,75452,36677,89073,43893,24944,61105,253,84788,14116,91758,18292,42657,8582,42380,62963,39573,60568,2497,52282,89607,95602,98533,7876,21329,81716,11566,18608,59691,72030,55781,34796,65676,65333,52992,46131,60001,84555,89762,41930,8398,54181,1457,76927,16469,37680,59601,37766,71379,63263,41564,15742,60778,2107,60342,21582,60381,50702,66886,365,42931,60635,93903,88484,79297,97666,67198,47818,86223,75774,57782,76203,3953,46767,76320,57897,41801,81976,60855,25980,321,33417,33768,96270,47368,39150,74240,43755,66611,60223,3726,96736,10597,52578,43679,83575,86050,1356,7420,6972,12657,96470,48004,55590,17002,15543,80905,50739,21488,32268,81791,26657,76556,77223,10349,49090,75144,6189,50132,26689,97212,2216,22676,18643,73521,634,14778,71920,59955,15135,49536,39849,44668,26911,68361,30567,95450,38612,38237,53955,42835,97589,17255,5799,21239,42456,70484,46704,52978,11479,78648,5627,62426,23414,65838,99912,85941,87217,84304,22380,39545,61926,84903,74864,39973,47622,50854,61112,72525,7139,20842,60482,85254,9222,31259,8457,97719,51821,1561,97165,72589,17431,99787,41830,17984,5568,43643,9950,67259,58534,49225,81810,21144,51861,5717,84339,23853,32563,20999,62277,29177,40952,55037,22172,70533,59637,38893,65881,38671,63835,64252,35975,34489,20375,80522,14372,83078,31140,26303,44921,43369,52001,59474,32828,27310,31299,35235,17556,39224,29340,61957,95190,83609,70304,95151,43541,56462,80451,2437,9093,85406,69435,87083,37885,49118,59455,54544,43796,94477,8264,29516,81249,57862,20153,38165,74979,97040,62423,61432,73690,16625,25130,50299,87664,25192,23563,85678,18705,58630,97662,74841,91464,98836,12962,81581,71410,33315,51909,1741,41072,74026,23939,67292,93547,17895,20617,25527,14917,64802,96113,80113,63586,55074,93379,19310,30544,93713,89536,60283,27542,70863,71120,30685,46696,91674,39660,9436,22290,47384,69184,26506,72804,6303,53567,12847,63835,53501,3065,98842,73987,81424,55654,50052,22054,46503,58622,8694,51199,92643,51652,47264,33378,8472,43438,21263,71155,72686,48186,72411,17761,52227,9006,30183,20050,68556,57970,73640,80974,26196,52796,4432,67598,12381,85897,14931,35228,1721,92068,74700,59907,68322,41903,4549,5141,93554,18390,30423,42732,45549,95300,46235,95737,48728,15072,24785,8053,42354,5739,70200,63937,31925,31117,50944,31334,94225,48749,59636,50648,33483,93425,20144,31850,5504,3674,61000,42657,36292,44228,55087,3693,82304,70850,63381,63625,99479,29202,2600,92811,81405,57865,41423,94418,74988,64466,5786,66898,13317,12742,25285,79867,5880,9936,68693,89861,76816,57020,39662,43427,51343,91580,65716,81268,87680,67215,76120,27806,5866,75866,42838,31586,96584,98750,4744,28078,15056,70336,6061,17694,64606,45907,56458,77847,69979,41050,32438,42241,31567,46971,44615,36418,20848,42360,53787,43044,12453,26322,248,63208,8018,98205,57602,10042,33413,23717,55234,24687,71767,81660,55462,48810,40046,95040,95857,87419,98900,53921,657,93003,91400,18760,18697,32187,10918,45859,67289,41121,33874,25215,5550,21617,73641,26441,60706,40900,37877,68196,77892,97818,23501,97225,94924,88107,83168,3927,5536,21539,71394,67351,50311,6589,62442,60751,91956,14113,26181,28266,35278,77335,32275,89701,31053,44984,30115,30617,32209,20725,27105,25819,39940,6435,39967,15165,99881,41666,26754,88493,52601,65440,86186,62276,47856,76945,28016,36298,1620,31469,94902,82542,32853,2888,67934,12469,66895,40418,4538,46130,73470,37878,19274,24705,65337,25036,62650,42446,86830,25692,76757,54260,70029,92679,26706,41915,31150,88854,96706,5121,75755,37125,82930,97579,25540,80065,24878,56678,61626,44353,28850,92678,62388,37213,58753,90634,10192,23236,63942,3012,55366,32985,6540,93606,50767,21048,25912,57603,52838,7758,55694,51240,66824,14518,66007,15256,69008,14367,12014,42601,79682,59359,95855,1535,78436,79229,77375,30303,23948,28715,62955,97788,37874,15526,19884,53829,48839,93769,18269,26650,86011,7070,28461,49167,44131,85075,230,33175,12817,75057,39939,26936,78364,53642,98807,38507,35586,46940,81121,99902,10785,59793,1475,62580,96244,9736,41210,80653,15667,25402,7342,41905,54176,47967,95527,83019,20678,31328,94918,27006,59055,48372,3170,52745,90408,88377,76759,46272,65458,99652,52584,67185,92133,99862,23443,24382,27801,2420,30947,76780,71039,62363,5220,52944,41678,2213,31435,63397,63250,8517,29853,70796,92235,73256,34115,73852,11485,3385,23486,24318,23732,98124,75877,96336,1791,74185,66904,46050,62082,17434,23928,25219,34425,37732,70926,17206,81707,89032,46099,34186,31544,18080,8491,17082,77476,47193,27678,65679,91586,96269,38569,60272,35754,78335,5089,37908,63416,4062,45667,57916,72097,24635,43017,41152,37015,98255,82531,83998,26916,4381,18402,27236,55848,13727,4411,65552,84359,40206,52916,92253,95610,16495,59505,68725,44781,67274,2976,91610,32237,64057,87544,58375,81375,79713,14458,74315,9488,72859,8141,70265,99930,33795,36095,17777,17737,52434,96095,3037,44669,97885,65788,14577,52841,14245,26230,59549,69384,75437,67687,17197,24891,64446,77311,66180,22774,89949,10992,20569,79404,38072,71349,64098,52345,97371,31649,10153,26959,8988,76344,47600,13347,37274,91667,78219,91799,94063,40247,57326,62914,12853,84994,27463,6123,18439,26349,63299,93275,30106,21786,28670,35776,69890,19369,26825,93151,9119,10663,16053,78907,84059,42407,8750,14384,25166,30662,94645,81091,41567,38380,79660,38594,62770,46578,54678,65368,51543,82588,40665,40934,64434,68480,42326,39383,77027,35833,74487,74626,55278,99504,35127,63531,95072,71982,51244,88027,18805,91149,70045,53715,79625,84544,24659,59583,40569,54760,69716,28190,76411,6916,36363,22239,98812,14386,31909,8380,28784,71333,15361,49005,465,85562,11607,25398,92375,36752,99844,21227,65965,55696,7130,19259,52339,77444,28073,39505,86105,20840,81780,37049,49642,12080,53271,71362,49229,5140,58056,94471,57122,33419,43983,25145,11966,12029,73155,25396,74099,58603,66402,64094,57085,66777,61012,10330,34618,59462,10484,22925,15999,15904,62257,18013,37364,5989,87589,96085,94220,93504,65300,14056,53688,35293,40198,6186,55886,17943,23611,85604,8551,7833,32928,81416,35680,20061,71104,49644,14045,35993,31328,81563,60399,65359,55359,7190,99331,82151,9588,10768,39158,90399,6653,87289,62159,23551,56892,21553,8648,55573,6334,49466,27868,40465,28985,19280,63704,67174,57919,85886,31207,48726,64698,42843,24338,89877,65647,8192,5828,68616,73246,35850,21093,20135,62116,28747,96428,47120,76592,84866,42533,29583,38866,89323,46913,1554,29434,7680,48341,51986,26838,39653,3998,32198,76375,59387,88964,51220,97794,83925,19734,840,68987,99916,22036,72470,95232,78176,54424,741,47520,46770,37646,46203,99846,34400,88439,68143,44644,77904,94954,83885,23817,22072,95130,17164,37431,56479,73599,54708,73836,31005,19455,55345,76417,53394,63419,43636,13818,66085,3441,86371,1751,51309,71247,52640,28277,47467,31574,26399,82632,30759,99510,72330,66198,79052,51285,76626,35275,1232,67877,84838,22106,35177,64654,20310,48638,8520,33737,1683,37953,32429,92742,24058,65629,97312,50491,3187,19866,56815,75662,85594,36967,12574,48261,68662,56667,91892,1970,88195,30260,54094,47039,1356,47103,34572,69178,45142,34844,79598,78278,62749,42493,62648,96738,66310,21733,94596,81431,53515,84287,69465,95010,26000,60760,77025,23420,95301,70490,57030,79581,56702,32124,10345,11753,10436,39743,99494,84201,65554,44685,79619,61982,14158,91240,78623,736,820,89504,20600,83237,63723,82569,46561,1338,75995,86117,78736,30036,7494,14115,66719,11307,86395,34220,48961,81465,74662,34824,58599,71237,88793,72235,87971,33388,11117,66236,14131,77925,70733,68376,12655,96896,76301,27691,64424,54158,28518,99834,20398,32665,70340,65182,12965,56719,30055,85628,58852,42602,50042,72067,56611,25140,89670,99869,84861,98838,87872,22722,33233,32643,28217,42343,46674,58620,8832,24497,38761,2318,89036,97621,72564,29456,98726,73954,16326,97312,25458,99262,82964,57639,43223,73108,11520,62052,91607,76277,10664,80012,27323,4035,53227,19279,94154,55443,49577,40403,28752,66660,83319,66528,96782,65926,72729,84436,58485,67450,1355,43280,56309,40036,93071,25870,4071,44859,21262,7131,33029,7763,28592,90976,81202,85147,63915,25221,9608,45418,79324,20319,15372,67871,63774,57484,6338,49416,36260,81812,25145,62293,59979,85515,55532,96684,65401,24225,85078,80873,29086,51534,48472,84263,61561,43028,93182,16468,79797,51945,30224,3407,65270,75360,10472,85092,97861,32941,76984,38999,15685,22684,8075,28909,39383,37962,28603,38439,63609,16762,56002,98412,90484]
[68460,91879,36597,48406,45552,29774,99922,50056,76873,96948,97065,88424,24302,26425,74052,67581,39559,8998,96343,97778,71166,84896,76277,65473,85053,26893,78671,54557,80936,78558,82375,22708,96804,43485,35901,22691,50553,94487,19269,34222,54280,81544,55841,70039,87821,38329,46395,74111,72898,77519,82154,82306,36301,76945,75266,75411,67620,35122,70944,32270,45708,53475,15903,31213,13463,87647,43179,52106,21952,93616,86371,94033,68174,97928,66037,62327,55193,50503,79185,82701,68202,49527,48758,59736,90353,86946,69521,39136,42360,78421,82053,98931,98897,95139,65457,72698,78169,76496,94287,64882,43227,97918,83874,92930,23154,96543,58749,96360,73641,83588,90969,89443,97526,24679,12039,63493,51487,79221,53671,32922,82821,48357,68164,84511,98399,73050,86878,97010,93343,56906,13122,87289,73880,98801,57054,89870,74357,90777,87314,72731,24560,89206,83497,76527,33534,74881,66674,44007,61306,93890,62048,99364,64296,80532,20125,30382,47123,57707,43700,97044,82909,92190,97022,58982,48350,67826,73990,16953,65986,44312,93623,32918,28426,7882,94349,92399,77849,89584,69447,65956,34301,85509,73788,81879,98510,3990,47782,90889,89823,75238,73799,92775,30832,78508,69843,90960,79341,95623,92405,87569,87201,43570,84678,86683,35205,72237,78825,77620,31702,88011,88452,84410,30303,90078,79777,54960,57669,32601,31516,23669,33437,55129,82679,87385,54264,41281,69265,41962,98435,42263,91994,88637,56222,79388,21749,36996,99278,98167,99566,80364,90356,99646,83754,85322,99833,96697,13538,82504,92020,64291,95902,48691,98238,99292,51462,67236,72122,98115,78022,51441,99799,93362,91989,90732,44616,91153,55670,77112,64595,91178,23371,27406,85611,42484,60310,81960,75342,46656,37648,67049,33976,56417,55714,22525,94677,57130,46424,99580,66160,43041,81031,52049,83581,83432,67080,69582,61501,40361,69206,64943,87497,76424,92321,77812,86498,82289,54673,34098,27732,94832,39133,88388,78629,62544,93752,67180,69590,97865,76942,80216,96692,4471,72170,68267,89397,68760,96551,68221,66742,77845,69442,91631,87851,82684,61433,57714,24717,98784,77797,93881,29701,68685,68139,83156,85225,84600,44619,59599,79456,52483,50147,74630,89819,88399,85380,85662,35574,95573,75685,65769,95251,65479,71562,95920,89942,40221,80234,76091,61044,77753,37446,89055,28992,46403,75343,59035,73960,82839,35340,10289,83332,73627,20356,78230,27608,81006,79054,53746,73762,65675,37392,85759,17470,79607,89101,46872,77488,95718,99121,88888,59776,27536,92194,89918,51035,56078,62757,90560,76779,75232,96577,75346,90650,80902,57168,62193,68197,60572,91605,81437,15572,34879,29603,42534,90614,66767,83707,87336,78995,31051,40241,88970,57420,98720,41964,93813,31804,79985,52033,87843,50770,39954,75269,72047,71677,86047,84693,85495,80711,61047,43649,92181,68332,45389,97675,75233,16397,72628,62879,61373,46128,83059,97466,79640,70034,15117,97265,99279,97067,93907,60873,82528,46986,98804,68858,85116,83169,92286,55433,50259,89585,85058,59985,16472,70208,33517,47537,97519,76027,83186,40827,44237,55900,88456,84795,90020,78987,59129,41951,76940,85562,58216,84494,87486,54267,44798,36489,89955,48778,78742,57036,91320,81569,78647,88912,15277,48232,51632,65313,27370,67529,55529,40500,99846,77266,95661,54574,65086,90380,47583,83752,24839,61974,74494,71974,41205,97687,87192,21640,75030,33736,78680,69905,97375,45515,57239,92923,22862,40252,61073,67712,96789,58196,95030,82991,32210,28542,84255,83720,75614,68093,83454,60667,97980,31194,74391,94812,50781,39270,89750,37085,99361,85151,69014,95516,10927,86703,99878,53689,54029,79181,46449,49291,68463,76582,54966,45443,91937,33696,43669,85067,73387,10572,50017,85668,28498,72696,97674,93728,96321,94439,96340,72400,91937,93623,85150,51657,58206,60389,93975,77060,84519,96092,52872,98214,96099,44800,88549,85327,54464,71130,81458,76224,98439,40123,51391,18644,80318,41226,65375,25051,95802,92472,78988,73562,95557,92960,59098,79577,96760,47179,83751,81130,19468,83807,86500,84200,90441,77651,30745,30338,73985,59222,38193,43865,70859,57896,98264,37041,91154,80967,94060,89390,98218,72227,43218,64061,97993,70297,48613,90766,86643,85620,98358,62582,47314,85160,24617,91700,93879,64244,66514,59810,55054,92489,41069,39431,89480,58814,83658,59072,90651,92213,42655,52741,51343,77117,81089,67107,55736,22262,74108,83401,95467,65092,62867,60704,97095,95077,40631,56776,94561,35314,93839,56620,53139,61872,91262,86479,48309,73170,57333,95022,88378,87860,53174,56297,18195,67659,95571,27777,73343,83783,77532,30508,93470,81809,70173,79137,69970,77637,62684,99422,82347,58552,27918,92828,5896,69954,88472,46488,90655,46132,79316,71739,78641,64663,95840,55379,36153,89654,73334,62782,95797,98297,52109,59009,54089,94577,82081,99186,57240,86393,56547,30509,73815,94876,70895,88304,34281,74692,65516,99218,74762,30930,75593,47774,97366,80612,89990,94453,64479,52042,75056,82687,90415,25742,43358,84027,51520,22693,97359,78475,62052,83897,78229,95683,30063,61981,46315,43051,63934,96054,58648,34292,63785,19142,47894,58882,44693,81332,31739,27812,88339,34307,90299,73526,96272,83547,81897,31551,64676,57422,46899,52471,60275,77874,90657,84154,28479,93511,46310,45141,25978,54554,91862,76062,81758,80827,75603,56712,67876,79721,68664,60558,62799,43586,57925,63428,82028,91238,97676,44724,73471,78845,56820,99357,19267,72945,64793,89741,81577,88345,50735,95787,97356,84642,18272,81701,87855,93442,40095,85630,68160,14088,62988,92744,88629,89114,69277,94392,72327,30384,63009,60704,72086,49769,50915,77308,61487,96523,42862,64291,64915,38662,55030,26241,12778,79905,92538,96152,81173,86535,96424,30612,98315,93141,83925,87829,58859,96469,94505,90733,68855,63375,70064,61651,87794,57102,92620,97398,89044,24454,86066,80390,82392,58466,42535,52395,11798,69120,50348,28955,99638,69390,84342,90970,51107,89192,53012,51794,19501,83778,68595,77475,97955,57282,78683,49043,54435,93808,97135,73792,15682,99740,83475,35813,71561,68196,65973,82681,90517,79409,66032,57466,57471,82317,99155,86398,98008,16032,75137,91446,46912,50350,80725,37320,86979,38729,69576,29208,61090,85219,80549,12669,66565,27272,25639,98224,85271,84098,54581,95162,42048,91105,67848,64453,54938,82675,70145,92083,49664,84522,92945,37290,40130,71529,98355,95824,24692,58609,81253,76593,50771,47172,49019,97449,3333,50423,59495,80981,61545,59966,41533,78194,89394,76409,85724,88936,51004,74938,51680,19604,35970,58432,90375,76119,76262,67444,84562,76876,86786,32293,65393,92273,31205,83869,89555,74185,66167,36913,66932,72648,83972,93077,30930,94438,98418,57274,49575,95651,98122,47277,49878,83578,91853,82797,73711,75249,48718,56227,97425,29254,37043,93768,16576,86657,75702,58738,81830,66488,88139,96656,85108,51484,60178,50802,73664,55255,53448,6469,88682,37331,55653,93642,99639,22917,65544,92334,44990,66513,76549,68445,41393,74132,80759,33703,50507,62173,81134,55862,80314,70323,73822,12610,49177,76792,98358,45188,45063,95431,83933,85603,53343,52401,97086,74620,89984,97270,96937,40265,77341,65680,65988,91845,84276,98144,99362,15246,46961,54448,80423,35315,84458,59753,38372,90388,98101,98753,97859,74677,30615,69014,69466,4767,70975,92514,93038,92895,98595,94686,74050,96823,79322,8018,77240,78087,45026,99352,49773,62585,1351,54899,35572,88037,81218,75463,65175,81918,98841,94589,52944,46903,77427,21967,91126,71328,47601,65987,77308,46361,25342,89602,91134,71318,78249,86703,93435,96545,55577,60365,93086,63704,77339,44958,53374,69597,91020,88347,65142,57985,26335,51240,95843,91339,47178,96930,86360,30729,55891,17962,76000,82999,49884,46597,62149,96526,40148,73343,29024,46488,57316,46461,71791,52446,14560,68519,50998,97123,42692,69408,73194,43937,76622,94895,72913,43464,68438,67038,62262,55945,54083,35341,83547,88324,9420,85812,17145,60242,80317,82601,50904,91195,79850,72591,53067,73543,73944,99626,48682,74828,81375,37510,44333,41170,41329,86484,37981,46371,65033,67977,93649,92223,73026,59162,44296,69713,69463,27180,63084,93987,88089,90779,81652,56959,90555,79616,48628,98676,42980,23091,77153,50996,78623,76146,93905,70021,79261,96945,32952,84184,53233,32657,82815,75684,92773,52748,35410,66713,78362,57126,77023,87184,99992,83017,98598,89170,30743,37076,64877,30493,94706,68983,81455,35096,52336,20287,27424,49093,82555,64018,79677,72853,50036,61536,90239,7959,69951,48756,89552,57774,70367,71064,88150,52546,94428,26113,89414,90503,79193,74057,48188,31324,84754,83098,82035,46789,71059,87779,89052,62104,95696,75459,70158,91185,82930,60186,77563,23649,74388,83032,52016,66157,84625,79505,95392,82646,75262,81549,88226,10356,54109,82509,70008,87542,68743,92577,90881,69217,50702,71008,48581,59851,27956,26625,59543,81836,76225,82498,47486,94569,90205,57410,22293,94382,44700,50411,98075,98668,91960,82238,73892,63809,78384,65480,16373,36497,36686,54228,95819,83106,34175,94866,84316,78422,98995,35155,86512,61774,84793,20209,8786,54234,89213,57778,83880,40031,72623,82312,64300,93329,78618,42257,78935,35218,31576,71226,98380,45620,55163,80953,32590,42839,90378,99721,82155,91073,73474,94191,62240,52746,62479,69529,75475,13252,82577,39980,28424,47486,78472,85572,47359,68327,32883,49359,9540,27871,32543,38346,62237,72451,43431,30104,66967,95248,97144,94703,92081,85597,64139,80870,72905,95735,36222,85132,22448,74495,56355,68530,90607,40530,51168,37492,85802,89664,48353,58458,61988,68654,94616,86394,83776,87919,63555,92487,82428,79869,97003,73711,86055,56501,66486,24421,79820,90908,25294,80243,50013,31483,99023,95144,42231,64912,89752,37974,31473,23356,98208,92108,93193,82285,88829,71048,89606,57331,94162,94364,90177,93015,87243,38086,63053,94347,86640,19298,97279,79214,78630,98776,61375,72326,45655,80517,72247,42918,26371,74960,61436,43788,17327,47333,38205,43853,50351,82049,63152,56588,90891,26148,45925,56526,72042,95812,75830,39028,39213,99540,63635,87934,87567,62812,78997,67791,64538,88603,78236,36693,83393,71320,62153,59460,96582,94505,18635,74894,91440,32126,71472,73148,97502,75535,54991,88493,74925,67661,99435,38250,60450,90148,66525,79714,98275,76472,29499,74759,77855,55288,30294,35764,77042,88640,9030,59461,50077,88203,42370,82587,93537,27155,79968,19597,83799,37814,83821,43081,28323,66905,61623,16304,76958,64348,82386,63341,68028,84974,81884,95466,59430,94436,73725,95857,53503,75403,42369,79822,73322,76994,90681,65231,75390,74934,93989,39205,67669,74578,89039,30768,79585,97131,73756,35784,98979,94861,55035,55033,95965,77917,96005,49666,75742,77714,99418,30012,53285,88833,20019,60783,95423,11352,97023,68374,47759,79891,83738,20916,39366,93796,37284,69751,10944,66656,31081,36758,95082,45097,59260,94213,48818,88139,49365,40997,98704,99118,29360,75164,37953,85276,5559,84785,60651,88899,97689,27874,72375,80235,67809,57399,52728,46082,68283,2317,88660,89387,77960,83492,22916,62634,78955,39153,87093,98663,94598,75144,70829,67727,74454,69208,65149,74044,78258,35091,73385,97840,36752,77575,18880,2643,81607,62435,34847,82443,80867,49408,33888,70483,83013,69890,73479,79576,44255,56475,62620,93216,55056,40409,85216,95137,82748,83168,84704,95792,57563,70043,17308,65516,17678,98847,50026,94185,98032,66001,90721,44092,46193,43574,86672,78948,53332,38892,81692,55846,96506,59307,87220,79212,95932,73795,49056,78232,74708,89678,55588,29353,68893,99138,92240,79041,69863,96147,53178,96600,30032,66799,42173,20196,8735,48535,94862,69845,61146,70910,91670,88404,22452,97701,35650,54464,61855,59908,50767,22013,11900,87375,33585,73487,95382,52053,93009,76521,95394,65853,98105,99719,92641,83872,75321,83756,80886,5053,93804,60545,96806,24136,82381,57127,76029,11705,51507,71646,19640,56070,46999,49018,43903,52122,93524,43268,35445,89807,58969,22478,85094,73528,67585,47181,56070,50353,73293,34944,14047,91609,28155,75633,94996,97974,80539,82040,60628,21703,94441,99615,33514,78604,73388,67934,85848,65005,96242,15652,91681,60198,97034,97591,12258,37346,19105,44725,16111,65649,54707,94517,17443,44923,44166,86863,66372,61304,91047,17033,96350,64168,96975,15218,48834,92154,69923,77463,39229,70044,50937,81201,54214,67644,96923,82643,80573,39499,83052,88488,29103,75827,37339,78457,90900,78408,95624,42660,79166,20401,76406,83095,80255,95921,90938,73521,18395,33521,33505,55403,48903,98699,95109,67559,79555,98594,93625,47538,94042,90832,51426,58838,83950,74412,65740,50592,93859,97074,74692,95360,68663,69700,39980,99461,63604,83596,77602,56947,23884,88557,88100,91682,87407,72001,74247,74087,53718,85048,35715,88409,55701,51957,62702,35736,89552,37906,89734,74808,87329,88015,92962,97946,63939,12683,79416,59055,66018,30590,55206,50045,86182,36507,75685,68535,79654,76939,66508,70916,71330,50651,35652,97446,59903,54117,27737,94662,94912,84252,24785,75623,99417,34020,99202,97395,90493,98175,98705,89272,42502,70021,88252,96651,48267,92890,98901,70042,79987,94000,38047,62992,65852,35655,89063,47097,56170,68070,83187,65466,50682,37881,89307,41221,33926,34532,97636,69154,37725,87301,73210,26362,97745,97869,99633,72110,30419,90681,37994,74981,38963,72308,96160,89920,69344,43397,64487,59411,94778,78740,92206,84117,82511,69883,98060,61806,81720,66335,42318,97890,18797,81458,66929,11554,42954,93828,9122,91809,39460,88996,23152,62128,25268,96540,40383,43568,11372,56211,33641,98658,91484,55192,28667,71615,59809,83036,41461,35943,89198,75233,96576,22057,86815,96888,60629,63861,38323,90413,24157,96674,44164,81670,87670,77945,74838,98456,72676,81631,77496,75133,92182,54158,33263,80944,83215,83427,57010,79251,35635,91024,67570,66348,85512,46236,18285,85031,72292,60771,80227,41866,18076,98168,24221,40775,83179,47333,36155,36157,98585,58850,62690,56203,30948,15926,46130,79557,20693,58043,41718,35134,30221,98310,45159,70942,99974,83432,57194,64849,88848,72839,83702,95871,91694,81343,59597,77720,87352,94774,71921,62053,92626,51479,89826,27105,79100,96395,77396,86788,86054,64725,90655,82307,48685,97725,97218,69634,76215,54602,91178,69605,88737,81507,99053,95339,83917,51421,52605,43988,72047,70041,34986,67483,95365,50261,74087,89316,47562,92891,94335,97460,99746,25587,65936,61969,97297,64148,83469,64972,88197,40782,73658,64329,46358,62499,85852,94703,67852,94811,49075,55091,96024,78979,51150,46118,93540,87428,22079,76472,86267,42733,60063,45175,97593,63169,46014,95190,71832,91801,98331,18189,70181,21230,24761,91112,33289,91319,7097,84052,59381,67425,77795,73964,76868,85316,30073,89722,63864,47784,61525,74241,82663,77108,51603,86339,81058,81877,82350,76482,68679,97758,98924,14831,53261,95630,47645,89707,91264,90751,87175,24797,63538,94964,77383,76900,81948,72251,91901,80665,81720,65154,63574,85687,65002,60446,91565,41175,20102,24793,28991,39551,76332,36199,53774,28851,90418,72345,90418,91719,93649,88447,64667,85864,76394,2099,70917,99502,91384,89420,88006,77503,89868,41717,93549,52358,77387,79224,55881,56433,74199,64355,38187,70063,75018,52735,65023,75862,63979,97995,22518,47276,55489,54146,41027,45465,82086,56189,36122,20239,85050,76964,99369,94291,77393,74331,91051,62404,67493,98703,44358,44284,90878,94402,72924,42809,98739,92290,77825,70852,86463,38239,56523,91393,86532,86300,64650,89937,69902,56695,96070,58539,31774,81365,38671,50868,86781,24139,65755,80457,81656,25902,65317,60424,46214,51378,73260,27569,80981,52076,61475,71066,60464,56675,70531,96980,73725,44472,86123,97740,76738,88857,74057,81883,34277,55103,49210,50668,26993,42457,20893,22624,15281,63659,74433,81191,99866,55332,85602,82999,93509,92570,80409,93297,66705,50432,28569,81628,33462,84729,99978,56412,41958,47827,85294,80726,89270,19797,90584,97420,58219,86928,98263,76711,23769,93914,71829,82775,80332,66412,64691,96361,75218,29626,79302,84874,39318,60532,31706,11350,87759,92645,56273,44631,50307,92359,95043,75823,96941,80080,72448,77929,88225,41254,99902,47175,81011,63632,72717,99419,77696,75412,56206,34331,69681,50820,88571,83478,50135,9869,78908,93563,78095,95495,71695,34798,26228,91481,89449,40196,78512,52173,52691,70083,54313,95007,35644,39308,33367,66251,77642,12874,45934,74498,13842,80132,94913,94987,67165,94027,23994,77420,80416,95375,26241,95991,49021,80756,64398,59544,78077,65545,64662,86753,90533,76259,44846,53904,43167,14763,83657,33845,95822,78541,69965,4659,37134,61221,81915,91127,61783,99413,76851,44807,97412,93188,97052,54014,57360,53229,18578,82856,23245,92013,84233,59541,20493,94942,72815,58288,13563,38664,14641,19902,71516,84266,76943,16233,21277,63453,76589,77445,97502,89362,90230,97817,44538,93634,92088,88521,73369,67197,33126,93661,72886,91567,66565,78965,87063,94958,90095,63490,96648,65539,81940,86789,82575,80003,53643,70460,28713,84819,58383,51684,77995,61647,60265,42283,76644,93750,42179,16684,81645,61731,32192,30284,79887,89701,70721,97897,86214,87546,98533,74997,10066,65544,83594,64985,33340,54975,99419,88039,76612,72528,45918,65246,26205,64208,92751,49713,90090,76586,55308,95014,61817,54592,75747,63703,4618,86332,89408,79506,51942,77172,50175,52634,91776,96294,51655,57745,80001,76742,39997,81438,93485,33814,82291,72401,91745,49199,59556,53438,42031,73330,11756,3753,74147,92326,65736,73828,85266,76542,92878,36722,83043,69293,59176,11597,70196,65349,61106,64348,91701,85519,59929,98881,56258,85606,84872,98777,75277,98109,68725,65288,98635,53803,65603,78699,83672,82721,98002,28960,65770,61932,94933,49046,21825,57453,97439,83040,58499,76953,40014,18963,72569,84337,43405,80680,50752,75307,60418,78049,93066,37891,63835,86047,56565,73838,98826,65996,98607,98447,20233,74313,98261,58147,87051,78712,52407,90811,57967,98269,79189,82261,26107,68071,23364,93075,94955,90290,70396,61326,8173,13826,58122,80867,16001,64406,26664,81042,79016,99560,83631,50872,71650,46817,60051,90296,38963,60457,77294,50139,73007,86632,64084,29311,80933,68025,27655,55070,41177,54745,59407,85329,76927,60611,49346,95793,89417,23357,18420,43736,87716,55166,80599,82672,93967,52419,90237,94880,81358,77052,87243,72248,40274,17690,85849,76075,24634,98967,53115,75661,31509,57877,97635,86369,63807,90172,46301,68823,65324,70936,77483,45966,50827,12219,27203,84592,51477,71293,74604,94091,56929,54320,35189,85801,82546,81978,30160,58125,50002,63561,99276,91602,92937,90162,40238,41453,67715,75590,63515,78183,97568,81077,90923,95803,45086,84614,12546,48742,70414,76226,96599,67464,99191,85017,96577,84192,82447,91139,95344,44523,49684,95142,4682,82648,76760,85262,46120,61398,88960,89246,81922,88582,60498,97254,75922,99341,46678,85934,78758,3720,19200,62975,36353,41364,89595,63061,79147,84123,73841,39916,47485,46536,96892,59777,61759,93557,73947,64407,70597,96124,15708,35248,69657,82445,64459,45438,94312,78355,53150,31512,54893,18653,89354,90273,81391,60367,49020,95378,15799,25136,96888,49590,90721,55695,76344,33566,41457,83644,94809,76686,61016,50948,47195,84648,80303,54376,65199,84004,79918,73496,19817,55705,40470,64275,96259,56939,76958,76976,76331,26751,93169,83215,80508,61734,66919,36461,31454,91083,78645,59735,55757,95909,90957,80337,77223,55348,93294,67058,98773,8608,66964,67949,78259,79528,82349,84758,96838,70918,13249,28806,25865,32053,79218,79305,73129,36634,58206,45153,98989,15128,50765,86934,63786,63229,83964,97812,20555,80542,13177,93910,27398,6667,83273,47362,60996,85797,95158,13851,52732,39671,57994,34633,95636,90219,77329,81422,99860,76120,83868,65802,7808,83034,18797,85747,19582,58619,92387,32463,41201,79562,38733,47515,86897,60632,93558,80310,76549,69125,70846,5719,73920,59532,44141,18292,90054,87816,37495,91210,62166,71556,31414,81776,71965,92465,61752,62079,68468,72699,71819,91351,58709,77269,52232,4948,89190,52345,70255,83331,76095,85602,28950,11901,41979,80051,78009,97881,18435,86755,65062,34228,99892,46830,71197,81478,88430,86537,6379,86742,59129,38084,55533,95535,39001,89390,47222,91845,35876,21101,39279,17911,68357,91077,88047,89638,88744,89828,93945,70602,57526,96323,96491,79999,82048,87983,31681,75823,83662,28084,70372,69740,46976,57803,99002,88939,63157,69495,57005,66369,92401,40084,72319,97689,83303,93066,73848,98612,13709,46578,62649,97751,26366,37093,92223,34911,58138,86411,97924,37026,51600,91959,77765,64841,92896,91890,84745,89205,81833,59008,87310,72091,71909,54234,46230,60914,39006,63552,97657,44061,73980,49010,90316,84748,91107,68039,51209,52627,67069,89252,83465,76599,99651,98205,81314,60498,67721,81773,68581,99294,45804,52456,56299,94664,72464,74470,97121,89757,41566,40769,94251,82337,35598,34635,76729,79429,86496,34621,73921,32372,15969,67001,53831,25445,69389,17111,85401,9208,63465,92114,43623,86664,67836,67616,83212,23479,30388,78268,85928,43940,55850,72466,89469,48592,26012,90755,45350,62614,88529,86044,41435,87844,84284,33033,97585,62146,46319,58532,92927,67203,50617,65686,97252,30077,54024,91507,78358,63837,85667,58662,60783,82281,44814,11148,65311,48895,46338,41204,52540,66047,69897,67216,33542,84506,81795,74977,76723,96531,86505,98657,60793,97089,25112,14396,61112,72831,74519,64030,81124,44504,36015,96921,82389,43222,53873,17271,97903,33171,82181,66365,95232,66332,71156,75235,56212,71508,91963,59729,43597,54570,30871,54069,90787,70766,75090,40769,71502,67325,78382,77225,44795,70572,77536,99996,84795,48961,95449,82932,57339,57060,96047,51680,22454,50938,89121,91336,82958,94830,66238,87105,96623,69775,75316,87742,85781,96378,95158,80638,88482,97607,61717,97310,52100,88313,76733,60636,82316,45649,19296,86861,62893,85543,73246,53121,47145,55052,89928,71212,34841,75505,87875,45999,73715,94577,83738,31501,74447,56856,74966,75456,78574,82277,91632,70785,53957,78852,34634,66809,79863,69275,37354,25020,80132,64298,42680,87636,62355,92769,71651,91819,43930,90241,42739,83526,82873,72614,74757,39366,18415,31588,99071,77350,85750,10776,92114,63807,98693,68205,52666,75117,76888,41512,82175,57651,62202,73390,68995,84516,68780,37581,99229,32817,33901,65869,94372,63030,13324,79035,37269,94289,65605,95144,45548,87947,28524,72023,77660,50581,14546,61581,82867,44983,94727,83772,45034,34870,80409,71333,89047,46247,84742,58301,89200,59150,95879,92748,84151,96031,97244,52175,77647,92424,48904,52022,79979,63730,53226,59026,95443,64998,30707,33796,57972,52409,59562,79198,33292,66981,33442,66480,23581,90422,90263,52166,79864,15486,85964,9545,68780,55336,64316,81661,66549,96545,92954,42781,86422,56854,18365,45646,80123,93342,80112,72308,96426,45862,70503,40159,78998,50850,46703,66528,94077,58303,92377,98947,32775,30608,98171,52665,90876,33137,76770,91634,75733,58668,75527,69330,46726,71656,78891,64410,89670,58833,79856,94154,27663,23401,81750,70959,67373,49936,16685,96358,78287,93088,83774,57553,94104,50063,94216,34117,98563,95976,27370,59052,99068,81206,12437,70723,32733,21564,73159,62641,55457,25793,50350,86106,87190,77718,31601,76335,93773,29201,91712,97930,34596,92712,28419,54098,38117,60294,86413,39224,9642,80462,39842,37302,99986,83977,80083,99315,56912,42403,89947,38443,39871,94773,83942,84243,86824,95648,79922,64553,73469,89492,95083,30893,92588,65537,82784,57896,95560,93619,17954,32231,70249,58088,15333,99075,92403,86515,79738,98065,67147,78804,88860,85890,85745,87200,87925,66720,98003,47517,50639,93099,76723,94220,41991,98087,94615,51342,62925,71867,85947,53173,16826,16937,83819,89180,95859,89018,88034,49936,42606,82512,79870,54458,97061,92959,38176,73885,79931,78577,81135,99897,22857,65447,87317,14074,52916,63309,19061,58750,74588,63491,40114,89390,71096,49930,51701,93832,82676,42677,32203,35349,89615,78312,23773,86067,89891,55452,79349,48904,21029,41345,95395,19082,67432,68738,55053,35711,23293,68046,94831,27554,72205,86069,95999,91083,83618,55650,75538,97050,50014,94276,85138,97097,67455,35421,27785,58713,18396,83652,67444,47804,4448,77820,87596,68235,14273,71972,66010,83494,94453,13025,90121,58741,7517,49379,88681,89330,95944,51965,15913,85473,53490,12152,98935,82188,76388,68030,95772,99854,88555,64514,68174,69005,91149,71432,58967,32502,98975,54206,64387,88896,56896,18810,33401,25603,45233,29846,68658,74057,82101,95021,61407,87474,39051,73857,43249,45555,61254,58318,75682,41618,92333,39732,64712,77049,94569,25712,97515,79507,88503,69935,41476,10973,45930,46025,31385,71668,61757,27269,66338,66163,69341,56421,49482,73123,63699,85960,94385,8443,97654,65252,83125,6765,92129,80132,86037,94124,80473,73424,52882,43442,95267,22293,72507,39311,87867,63953,41060,92284,94959,81685,68733,65541,10870,94741,71678,80599,56841,63276,14928,66592,47693,83279,72601,71939,57948,96734,42252,72445,61854,83743,49373,10445,75972,68780,94294,70432,71607,81985,71262,36397,77730,26030,87512,96555,52886,52925,8737,53902,49844,93026,69667,49768,97159,98308,89315,58922,57323,82912,39351,46998,52655,39076,35323,92707,82013,86152,84932,58185,76487,83220,82304,15956,55922,89414,83739,76929,76056,96788,21175,90262,93632,26754,66562,45952,70794,10915,68019,90382,93057,98759,58025,94576,78438,91462,94796,91479,96700,96191,55092,74865,95706,74723,84824,83398,81820,77176,51179,38012,13446,86193,98608,77722,79459,96035,51327,70585,65391,96713,92914,70355,93589,98915,49189,99040,97203,56517,51121,98685,99466,74545,54679,63674,35829,59514,93440,31941,97026,92672,83377]
1651505078
[38,14,1,11,33,38,21,11,25,14,27,29,40,11,10,40,14,16,25,35,33,11,30,31,7,36,11,1,39,5,11,8,22,20,29,31,27,8,38,32,28,32,22,19,26,24,20,25,5,34,24,18]
[33,14,15,32,26,37,35,32,30,28,24,29,13,22,39,9,26]
39
[15,8,19]
[38,36,23]
328
 */